The present invention relates to graphics processing in a computer system, and more particularly to a method and system for more efficiently rendering a graphical image.
A conventional computer graphics system can display a graphical image on a display. The display includes a plurality of display elements, known as pixels, typically arranged in a grid. In order to display objects, the conventional computer graphics system typically breaks the objects into a plurality of polygons. The conventional system then typically renders the polygons in a particular order. For a three-dimensional scene, the polygons are generally rendered from back to front as measured from the viewing plane of the display. Similarly, a two-dimensional scene can be displayed where polygons are rendered based on their layer. Shallower layers occlude deeper layers.
For example, FIG. 1 is a block diagram of a display 1 depicting a graphical image. The display includes a plurality of pixels 8, only one of which is labeled. The graphical image includes primitives 2, 3, 4, 5, and 6 which may be part of one or more objects. Each of the primitives 2, 3, 4, 5, and 6 may cover several pixels and includes a plurality of fragments. Each fragment includes data for a pixel intersected by the corresponding primitive. Thus, a fragment may include data relating to the color, texture, xcex1 values, and depth values for a particular primitive and a particular pixel.
One conventional method used in rendering the graphical image renders the image primitive by primitive in a particular order. For a three-dimensional scene, the primitives are generally rendered from back to front as measured from the viewing plane of the display. Similarly, a two-dimensional scene can be displayed where primitives are rendered based on their layer. Shallower layers occlude deeper layers. For example, the primitive 2 might be rendered first, followed in order by primitives 3, 4, 5, and 6.
FIG. 2A depicts another conventional method 10 for rendering a graphical image. FIG. 2B depicts a display 20 including the primitives 2, 3, 4, 5, and 6 which are rendered using the conventional method 10. Referring to FIGS. 2A and 2B, in order to render the graphic image, portions of the display 1 are rendered one at a time. Thus, a plurality of tiles, each tile having a fixed size, is defined, via step 12. A tile is typically a two-dimensional rectangle containing n xc3x97m pixels. The tiles 21, 22, 23, 24, 25, 26, 27, 28, and 29 are depicted in the display 20. The primitives 2, 3, 4, 5, and 6, or portions thereof, are then rendered tile by tile and primitive by primitive. For example, the portion of the primitive 2 in tile 21 is rendered first. When tile 21 has completed rendering, the portion of the primitive 4 in tile 22 is rendered. When tile 22 is completed, the portions of the primitives 4 and 6 in tile 23 are rendered. This process continues, rendering the graphical image primitive by primitive and tile by tile, until all primitives in all tiles have been rendered.
Although these conventional methods function, one of ordinary skill in the art will readily realize that it is desirable to provide data for an image in raster order. Furthermore, it would desirable if the image is efficiently rendered. Consequently, STELLAR SEMICONDUCTOR of San Jose, Calif. developed a system for rendering a graphical image pixel by pixel, in raster order. Raster order is from left to right and top to bottom across the display 1. This system is described in U.S. patent application Ser. No. 08/624,261, entitled xe2x80x9cMETHOD AND APPARATUS FOR IDENTIFYING AN ELIMINATING THREE-DIMENSIONAL OBJECTS VISUALLY OBSTRUCTED FORM A PLANAR SURFACExe2x80x9d filed on Mar. 29, 1996 now Pat. No. 5,926,181, and assigned to the assignee of the present application and in co-pending U.S. patent application Ser. No. 08/624,260, entitled xe2x80x9cGRAPHICS PROCESSORS, SYSTEM AND METHOD FOR GENERATING SCREEN PIXELS IN RASTER ORDER UTILIZING A SINGLE INTERPOLATORxe2x80x9d filed on Mar. 29, 1996 now Pat. No. 5,933,210, and assigned to the assignee of the present application.
FIG. 3 depicts a high-level block diagram of one embodiment of such a computer graphics system 50. The system 50 includes a central processing unit (CPU) 52, a display 54, a user interface 56 such as a keyboard or mouse or other communicating device, a memory 58, and an image generating unit 60 coupled with one or more buses 58. The display 54 includes a display, such as the display 1. The display 14 also includes a display memory 55 to which data for pixels are written prior to being shown on the display 1. In order to display graphical images, the objects are broken into polygons to be used in rendering the objects. In a preferred embodiment, the polygons are rendered in raster order. That is, portions of the polygons are rendered pixel by pixel in the order of the pixels in the display 54.
The image generating unit 60 is used in rendering the graphical image. The image generating unit includes an interface 61 connected to the bus 58. The interface 61 transmits data to a data processing unit 62. The block of processors 64 identifies data describing portions of primitives (xe2x80x9cintersecting primitivesxe2x80x9d) which intersect the area extending along a z-axis from a selected pixel in an x-y plane corresponding to a screen of the display 14. The block of processors 64 may include a number of processors, allowing intersecting primitives to be processed in parallel. By processing the primitives in parallel, the block of processors 64 can provide an indication of the fragments that intersect pixels currently being processed in a particular scan line. An obstructed object identifier/removal unit (Quick Z) 66 receives at least a portion of the fragment from each intersecting polygon associated with the selected pixel and removes portions of the fragments for intersecting polygons that are obstructed.
The interpolator 68 receives the remaining fragments for the intersecting polygons for the selected pixel and interpolates the data, including interpolating texture, color, and alpha values for the fragment. The interpolator 68 also provides a coverage mask for each fragment. The coverage mask indicates the portion of the pixel that the fragment covers. The fragments for remaining intersecting polygons are provided by the interpolator 68 to a hardware sorter 70. The hardware sorter 70 sorts the fragments for the intersecting polygons based on the value of a key such as the z value, or depth value, for the fragment.
An antialiasing/blending/accumulating unit 72 performs antialiasing using the mask provided by the interpolator 68. The antialiasing unit 72 may multiple units used in antialiasing, accumulating data, and blending data. The antialiased data is provided to the display 14 pixel by pixel in raster order.
Although the above-mentioned co-pending applications function well for their intended purpose, the processors in the block of processors 64 may overflow. In order to render the images in raster order, a number of the primitives intersecting pixels in a particular scan line (a row of pixels on the display 1) are processed in parallel. There are also a finite number of processors in the block of processors 64. For example, in one embodiment, sixty-four processors are provided in the block of processor block 64. When a particular scan line contains a large number of primitives, more primitives than processors in the block of processors 64 may be attempted to be processed in parallel. The block of processors 64 may then overflow. Such an overflow is undesirable. Furthermore, efficient rendering of the graphical image is desired.
Accordingly, what is needed is a system and method for efficiently rendering a graphical image. It would be desirable if an overflow of processors can be avoided. The present invention addresses such a need.
The present invention provides a method and system for providing a graphical image on a display of a system. The graphical image is provided from data describing a plurality of primitives. The display includes a plurality of pixels. The method and system comprise providing a plurality variable-sized bins containing the plurality of primitives and rendering the plurality of primitives by rendering each of the plurality of variable-sized bins variable-sized bin by variable-sized bin. In a first aspect, the system also includes a plurality of processors for processing a portion of the plurality of primitives in parallel. In this aspect, the variable-sized bin providing step further includes the steps of storing the plurality of primitives in a plurality of bins and determining if a part of a portion of the plurality of bins can be combined without causing the plurality of processors to overflow. In this aspect, the method and system also comprise combining the part of the portion of the plurality of bins to provide the plurality of variable-sized bins if the part of the portion of the plurality of bins can be combined without causing the plurality of processors to overflow. The plurality of variable-sized bins can include fewer bins than the plurality of bins. In another aspect, the method and system further include determining a plurality of bins for a previous frame and providing the plurality of bins containing the plurality of primitives.
According to the system and method disclosed herein, the present invention efficiently separates the graphical image into variable-sized bins that can be separately rendered without overflowing the system.